//零钱兑换 II

class Solution {
public:
    int change(int amount, vector<int>& coins) 
    {
        //dp[i] 总金额为i的组合数
        vector<int>dp(amount+1,0);
        dp[0]=1;
        for(int i=0;i<coins.size();i++)
        {
            for(int j=coins[i];j<=amount;j++)
            {
                dp[j]=dp[j]+dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};
//组合总和Ⅳ

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) 
    {
        //dp[i] 重量为i的组合数
        //返回dp[target]即可
        vector<unsigned long long>dp(target+1,0);
        dp[0]=1;
        // for(int i=0;i<nums.size();i++)
        // {
        //     for(int j=nums[i];j<=target;j++)
        //     {
        //         dp[j]+=dp[j-nums[i]];
        //     }
        // }
        for(int j=1;j<=target;j++)
        {
            for(int i=0;i<nums.size();i++)
            {
                if(j>=nums[i])
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[target];

    }
};
//零钱兑换
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) 
    {
        //dp[i] 金额为i的最少硬币个数
        //dp[i]=min(dp[i],dp[i-nums[i]]+1)
        vector<int>dp(amount+1,INT_MAX);
        dp[0]=0;
        for(int i=0;i<coins.size();i++)
        {
            for(int j=coins[i];j<=amount;j++)
            {
                if(dp[j-coins[i]]<=INT_MAX-1)
                dp[j]=min(dp[j],dp[j-coins[i]]+1);
            }
        }
        return dp[amount]==INT_MAX?-1:dp[amount];
    }
};
//完全平方数

class Solution {
public:
    int numSquares(int n) 
    {
        vector<int>dp(n+1,INT_MAX);
        dp[0]=0;
        for(int i=1;i<=n/i;i++)
        {
            for(int j=i*i;j<=n;j++)
            {
                dp[j]=min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
};
//单词拆分
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) 
    {
        //dp[j] s的前j个字符能否被wordDict拼成
        vector<bool>dp(s.size()+1,false);
        // s就是背包 由里面的下标截成的字符就是物品
        // 需要确定的就是物品是否在物品集里面
        unordered_set<string>words(wordDict.begin(),wordDict.end());
        dp[0]=true; 
        for(int j=1;j<=s.size();j++)
        {
            for(int i=0;i<j;i++)
            {
                string tmp=s.substr(i,j-i);
                if(words.find(tmp)!=words.end() && dp[i])
                dp[j]=true;
            }
        }
        return dp[s.size()];
    }
};